package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-19
 */

import java.util.ArrayDeque;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 */
public class leetcode160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ArrayDeque<ListNode> la = new ArrayDeque<>();
        ArrayDeque<ListNode> lb = new ArrayDeque<>();
        ListNode pre = null;
        while (headA!=null){
            la.add(headA);
            headA = headA.next;
        }
        while (headB!=null){
            lb.add(headB);
            headB = headB.next;
        }
        while (!la.isEmpty() && !lb.isEmpty()){
            ListNode tmpA = la.removeLast();
            ListNode tmpB = lb.removeLast();
            if (tmpA==tmpB && tmpA!=null && tmpB!=null) pre = tmpA;
            else break;
        }

        return pre;
    }
}
